1. Field of the Invention
The present invention relates to the field of integrated circuit (IC) design. More specifically, the present invention relates to the optimization of placement and routing for an IC design.
2. Background Information
Over the years, because of the ever increasing complexity of IC designs, IC designers have become more and more reliant on electronic design automation (EDA) tools to assist them in designing ICs. These assistance span the entire design process, from synthesis, placement, routing, to layout verification.
In the art of placement and routing, i.e. placement of components and routing of connections connecting the various components, various techniques are known. For examples, in U.S. Pat. No. 5,818,729, issued to Wang et al, a method and system for placing cells using "quadratic placement" and a "spanning tree" model was disclosed; in U.S. Pat. No. 5,072,402, issued to Ashtaputre et al., a method for routing interconnections using a "channel" approach is disclosed; and in U.S. Pat. No. 5,550,748, issued to Xiong, a method for "delayed" routing, to satisfy timing constraints, using a "region search" approach is disclosed.
In recent years, various techniques for "jointly" performing placement and routing have also become known. For examples, in U.S. Pat. No. 5,798,936, issued to Cheng, a placement method including look ahead for routing congestion was disclosed; in U.S. Pat. No. 5,838,583, issued to Varadarajan et al., a "joint" method for optimizing placement and routing was disclosed; and in U.S. Pat. No. 5,847,965, issued to Cheng, a "joint" area based method for placing and routing an IC was disclosed.
While each of these prior art techniques has its own advantages, they all share at least one common disadvantage in that they do not adequately address the placement and routing need of sub-micron ICs. Increasingly, interconnect delay has become the primary obstacle preventing sub-micron ICs from realizing the full benefit of these ICs' further increase in compactness for their operating speed. Thus, a placement and routing technique that more adequately addresses the need of sub-micron IC designs is desired.